{"cells":[{"metadata":{"trusted":true},"cell_type":"code","source":"import math\n\ndef pgcd(a, b):\n    \"\"\"\n    Calcule le Plus Grand Commun Diviseur (PGCD) de a et b\n    en utilisant l'algorithme d'Euclide.\n    \"\"\"\n    while b:\n        a, b = b, a % b\n    return a\n\ndef pollard_p_minus_1(n, B):\n    \"\"\"\n    Tente de factoriser un nombre n en utilisant l'algorithme p-1 de Pollard\n    avec une borne B.\n\n    Args:\n        n (int): Le nombre à factoriser.\n        B (int): La borne de friabilité (limite pour les petits facteurs premiers).\n\n    Returns:\n        int or None: Un facteur de n s'il est trouvé, sinon None.\n    \"\"\"\n    # Étape 1: Choisir une base. On prend généralement a = 2.\n    a = 2\n\n    # Affiche les paramètres de départ\n    print(f\"▶️ Tentative de factorisation de N = {n}\")\n    print(f\"▶️ Utilisation de la base a = {a} et de la borne B = {B}\\n\")\n\n    # Étape 2 & 3: Calculer a^k mod n de manière itérative.\n    # On élève 'a' à la puissance des nombres premiers q <= B.\n    # C'est plus efficace que de calculer k = B! directement.\n    \n    # On utilise un simple générateur de nombres premiers\n    # On commence avec 2\n    print(\"Calcul de M = a^k mod N...\")\n    if 2 <= B:\n      a = pow(a, 2, n)\n    \n    # Puis on parcourt les nombres impairs\n    q = 3\n    while q <= B:\n        # On élève a à la puissance du premier q\n        a = pow(a, q, n)\n        q += 2 # On passe au prochain nombre impair\n        # Note : cette boucle simple inclut des non-premiers,\n        # mais cela ne compromet pas le résultat, bien que ce soit moins optimal\n        # qu'un vrai crible à nombres premiers.\n\n    print(f\"Calcul terminé. M = {a}\\n\")\n\n    # Étape 4: Calculer le PGCD de (a - 1) et n.\n    d = pgcd(a - 1, n)\n    print(f\"Calcul du PGCD(M - 1, N) = PGCD({a-1}, {n})...\")\n\n    # Étape 5: Analyser le résultat.\n    if 1 < d < n:\n        return d  # Succès ! Un facteur a été trouvé.\n    elif d == 1:\n        print(f\"❌ ÉCHEC : Le facteur premier p de N est tel que p-1 n'est pas {B}-friable.\")\n        print(\"💡 Conseil : Essayez d'augmenter la valeur de la borne B.\")\n        return None\n    elif d == n:\n        print(\"❌ ÉCHEC : Cas rare où tous les facteurs ont été trouvés en même temps.\")\n        print(\"💡 Conseil : Essayez avec une autre base que a=2.\")\n        return None\n    else: # d=0, ne devrait pas arriver\n        return None\n\n\n# --- Programme Principal ---\nnombre_a_factoriser_2 = 19987454465465465465641\nborne_2 = 100 # On a besoin d'une borne plus grande ici\n\nfacteur_2 = pollard_p_minus_1(nombre_a_factoriser_2, borne_2)\n\nif facteur_2:\n    facteur2_2 = nombre_a_factoriser_2 // facteur_2\n    print(f\"\\n✅ SUCCÈS ! Un facteur a été trouvé : {facteur_2}\")\n    print(f\"La décomposition est : {nombre_a_factoriser_2} = {facteur_2} x {facteur2_2}\")\n\n","execution_count":8,"outputs":[{"output_type":"stream","text":"▶️ Tentative de factorisation de N = 19987454465465465465641\n▶️ Utilisation de la base a = 2 et de la borne B = 100\n\nCalcul de M = a^k mod N...\nCalcul terminé. M = 17032148596230296729894\n\nCalcul du PGCD(M - 1, N) = PGCD(17032148596230296729893, 19987454465465465465641)...\n\n✅ SUCCÈS ! Un facteur a été trouvé : 3311\nLa décomposition est : 19987454465465465465641 = 3311 x 6036682109775133031\n","name":"stdout"}]},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"}},"nbformat":4,"nbformat_minor":2}